package demo7;

import java.util.*;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

public class Solution {

//    //1.剑指 Offer II 068. 查找插入位置(二分法)
//    public int searchInsert(int[] nums, int target) {
//        int left = 0;
//        int right = nums.length - 1;
//        int mid = 0;
//        while(left < right) {
//            mid = (left + right) / 2;
//            if(nums[mid] < target) {
//                left = mid + 1;
//            } else if(nums[mid] > target) {
//                right = mid - 1;
//            } else {
//                return mid;
//            }
//        }
//        mid = (left + right) / 2;
//        if(nums[mid] == target) {
//            return mid;
//        } else if(nums[mid] < target) {
//            return mid + 1;
//        } else {
//            return mid;
//        }
//    }

    //1.剑指 Offer II 068. 查找插入位置(优化二分)
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right) {
            int mid = left + ((right - left) >> 2);
            if(nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return left;
    }

    //2.剑指 Offer II 032. 有效的变位词(字典)
    public boolean isAnagram(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();
        if(len1 != len2) {
            return false;
        }
        int[] map1 = new int[26];
        int[] map2 = new int[26];
        boolean flag = false;
        for(int i = 0; i < len1; i++) {
            char chs = s.charAt(i);
            char cht = t.charAt(i);
            if(chs != cht) {//判断字母是否不完全相同
                flag = true;
            }
            map1[chs - 'a']++;
            map2[cht - 'a']++;
        }
        return flag && Arrays.equals(map1, map2);
    }

//    //4.剑指 Offer II 072. 求平方根(二分法)
//    public int mySqrt(int x) {
//        if(x == 1) {
//            return 1;
//        }
//        int max = x;
//        int min = 0;
//        while(max > min + 1) {
//             int mid = min + (max - min) / 2;
//             if(mid > x / mid) {
//                 max = mid;
//             } else if(mid < x / mid) {
//                 min = mid;
//             } else {
//                 return mid;
//             }
//        }
//        return min;
//    }

    //5.剑指 Offer II 043. 往完全二叉树添加节点(构造器bfs)
    class CBTInserter {

        //用链表来存储
        private List<TreeNode> list = new ArrayList<>();
        private int index = 0;

        public CBTInserter(TreeNode root) {
            list.add(root);
            int cur = 0;
            while(list.get(cur).left != null || list.get(cur).right != null) {
                if(list.get(cur).left != null) {
                    list.add(list.get(cur).left);
                }
                if(list.get(cur).right != null) {
                    list.add(list.get(cur).right);
                }
                cur++;
            }
        }

        public int insert(int v) {
            if(index == 0) {
                while(list.get(index).left != null && list.get(index).right != null) {
                    index++;
                }
            }
            //判断插入位置
            TreeNode node = new TreeNode(v);
            if(list.get(index).left == null) {
                list.get(index).left = node;
            } else {
                list.get(index).right = node;
            }
            list.add(node);
            //判断当前结点是否已满
            int ret = list.get(index).val;
            if(list.get(index).left != null && list.get(index).right != null) {
                index++;
            }
            return ret;
        }

        public TreeNode get_root() {
            return list.get(0);
        }
    }

    //6.剑指 Offer II 072. 求平方根(数学)
    public int mySqrt(int x) {
        if(x == 1) {
            return 1;
        }
        int left = 0;
        int right = x;
        while(left < right - 1) {
            int mid = (left + right) / 2;
            if(mid > x / mid) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return left;
    }

}

//7.剑指 Offer II 031. 最近最少使用缓存
class LRUCache {

    //双向链表
    class LinkNode {
        public int key;
        public int value;
        public LinkNode next;
        public LinkNode prev;

        public LinkNode() {

        }

        public LinkNode(int key, int value) {
            this.key = key;
            this.value = value;
        }

    }

    private Map<Integer, LinkNode> cache;
    private LinkNode head;
    private LinkNode tail;
    private int capacity;
    private int usedSize;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new LinkNode();
        this.tail = new LinkNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if(cache.containsKey(key)) {
            LinkNode cur = cache.get(key);
            //从中间删除这个结点，并头插
            cur.prev.next = cur.next;
            cur.next.prev = cur.prev;
            insertHead(cur);
            return cur.value;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if(cache.containsKey(key)) {
            //修改当前结点的值
            LinkNode cur = cache.get(key);
            cur.value = value;
            //从中间删除这个结点，并头插
            cur.prev.next = cur.next;
            cur.next.prev = cur.prev;
            insertHead(cur);
        } else {
            //创建该结点，并放入哈希表中
            LinkNode cur = new LinkNode(key, value);
            cache.put(key, cur);
            if(usedSize < capacity) {
                //若实际长度小于容量，直接头插新结点即可
                insertHead(cur);
                usedSize++;
            } else {
                //从cache中删除
                cache.remove(tail.prev.key);
                //删除尾结点，并将新结点头插
                deleteTail();
                insertHead(cur);
            }
        }
    }

    //尾删
    public void deleteTail() {
        LinkNode del = tail.prev;
        del.prev.next = del.next;
        del.next.prev = del.prev;
    }

    //头插
    public void insertHead(LinkNode cur) {
        head.next.prev = cur;
        cur.next = head.next;
        cur.prev = head;
        head.next = cur;
    }

}

class Main {
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.get(1);
        lruCache.put(3,3);
    }
}

//3.完全二叉树插入器(BFS)
class CBTInserter {

    private List<TreeNode> list = new ArrayList<>();
    private int index = 0;

    public CBTInserter(TreeNode root) {
        list.add(root);
        int cur = 0;
        while (cur < list.size()) {
            TreeNode node = list.get(cur);
            if (node.left != null) list.add(node.left);
            if (node.right != null) list.add(node.right);
            cur++;
        }
    }

    public int insert(int val) {
        if(index == 0) {
            while (list.get(index).left != null && list.get(index).right != null) {
                index++;
            }
        }
        TreeNode node = new TreeNode(val);
        if(list.get(index).left == null) {
            list.get(index).left = node;
        } else {
            list.get(index).right = node;
        }
        list.add(node);
        int ret = (list.size() - 2) / 2;
        if(list.get(index).right != null) {
            index++;
        }
        return list.get(ret).val;
    }

    public TreeNode get_root() {
        return list.get(0);
    }
}
